home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / seqdemos / lqueen.icl < prev    next >
Text File  |  1992-08-07  |  2KB  |  79 lines
  1. MODULE lqueen;
  2.  
  3. <<
  4. The Queens Problem.
  5.  
  6. Or: How to put n queens on a n*n chessboard in such a way that they
  7. cannot attack each other.
  8.  
  9. The result of this program is the number of possible solutions for
  10. the queens problem for a certain boardsize together with one solution.
  11. When BoardSize is 8 the result will be: (92,[4,2,7,3,6,8,5,1]),
  12. which means the queens are on a4, b2, c7, d3, e6, f8, g5 and h1.
  13.  
  14. This program is the fastest possible algorithm (?) for the Queens problem
  15. in Clean without strictness annotations added by the programmer. It runs
  16. about 40% slower than the fastest possible algorithm (?) with strictness
  17. annotations added by the programmer (squeen.icl).
  18. >>
  19.  
  20. IMPORT deltaI, deltaB;
  21.  
  22. MACRO
  23.     
  24.     BoardSize -> 8; == The size of the chessboard.
  25.  
  26. RULE
  27.  
  28. ==  Miscellaneous list functions.
  29.  
  30. ::  Length [x]      -> INT;
  31.     Length [hd|tl]  -> ++ (Length tl);
  32.     Length []       -> 0;
  33.  
  34. ::  Head [x]     -> x;
  35.     Head [hd|tl] -> hd;
  36.  
  37.  
  38. ==  Finding all solutions for the queens problem.
  39.  
  40.     
  41. ::  Queens INT [INT] [[INT]] -> [[INT]];
  42.     Queens row board boards -> [board | boards] , IF > row BoardSize
  43.                             -> TryCols BoardSize row board boards;
  44.  
  45. <<  The second alternative of TryCols is added to make sure Save is never
  46.     called with an empty list.
  47. >>  
  48. ::  TryCols INT INT [INT] [[INT]] -> [[INT]];
  49.     TryCols 0 row board boards
  50.     ->  boards;
  51.     TryCols col row [] boards
  52.     ->  TryCols (-- col) row [] queens,
  53.         queens: Queens (++ row) [col] boards;
  54.     TryCols col row board boards
  55.     ->  TryCols (-- col) row board queens , IF Save col 1 board                        
  56.     ->  TryCols (-- col) row board boards,
  57.         queens: Queens (++ row) [col | board] boards;
  58.  
  59. <<  Save will never be called with an empty list as third argument, so
  60.     no alternative for that case is needed, which means the strictness
  61.     analyser can now deduce strictness of the first and second argument
  62.     of Save.
  63. >>
  64. ::  Save INT INT [INT] -> BOOL;
  65.     Save  c1 rdiff [c2]
  66.     ->  AND (<> cdiff 0) (AND (<> cdiff rdiff) (<> cdiff (- 0 rdiff))),
  67.         cdiff: - c1 c2;
  68.     Save  c1 rdiff [c2|cols]
  69.     ->  FALSE , IF = cdiff rdiff || = cdiff 0 || = cdiff (- 0 rdiff)
  70.     ->  Save c1 (++ rdiff) cols,
  71.         cdiff: - c1 c2;
  72.  
  73. <<  The Start Rule: Calculate the list of solutions, show the first
  74.     solution and the length of that list.
  75. >>
  76. ::  Start -> (INT,[INT]);
  77.     Start -> (Length solutions, Head solutions),
  78.                 solutions: Queens 1 [] [];
  79.